import queue

import numpy as np
from collections import Counter
import random
import math
import re
from typing import List, Tuple, Dict, Optional
import time


class TGP_GA:
    def __init__(self, start=1, goal=12, pack_num=20, max_gen=100, hay_flick=6, mutationP=0.5, crossP=0.5, n=None,
                 dis_map=None):
        #  public
        if n is None:
            n = [1, 20, 5, 7, 8, 12]
        if dis_map is None:
            dis_map = [[]]

        # 任务参数
        self.max_gen = max_gen
        self.start = start
        self.goal = goal
        self.pack_num = pack_num
        self.hay_flick = hay_flick
        self.mutationP = mutationP
        self.crossP = crossP
        self.n = n
        self.dis_map = dis_map
        self.cur_cost = 0
        self.key_nodes = n  # 城市集合
        # 城市序列，用于shuffle，随机生成序列
        self.nums = [key_node for key_node in self.key_nodes if key_node != self.start and key_node != self.goal]

        # 遗传算法相关数据
        self.BASE = 10000.0
        self.get_random_10000 = lambda: random.randint(1, 10000) / self.BASE
        self.uniform_int_distribution = lambda: random.randint(1, len(self.key_nodes) - 2)
        self.get_random_node_size = lambda: self.uniform_int_distribution()
        self.cur_gen = 1
        self.packs = [self.get_solution(path=[1, 20, 5, 7, 8, 12], sum=120, f=0.70, p=0.6, gen=0),
                      self.get_solution(path=[1, 5, 7, 8, 20, 12], sum=132, f=0.10, p=0.4, gen=1),
                      self.get_solution(path=[1, 7, 5, 8, 20, 12], sum=150, f=0.26, p=0.2, gen=2),
                      self.get_solution(path=[1, 8, 20, 7, 5, 12], sum=100, f=0.33, p=0.8, gen=3),
                      self.get_solution(path=[1, 20, 8, 5, 7, 12], sum=140, f=0.21, p=0.1,
                                        gen=4)]  # 种群，注意，源代码中的种群由pack改为packs，便于区分----------------------------------------------------

        # 中间结果相关数据
        self.displays = []
        self.cross_data_temp = self.get_display()['init_cross_data']()
        self.cross_action_temp = self.get_display()['init_cross_action']()
        self.mutation_data_temp = self.get_display()['init_mutation_data']()
        self.mutation_action_temp = self.get_display()['init_mutation_action']()
        self.record = []  # 传代统计队列
        self.regex = {"^(\\d+) (\\d+) (\\d+)$"}  # 读入数据的正则表达式

    # 定义结点，x，y好像可以叉出去了
    @staticmethod  # 静态方法，不需要实例化类就能访问
    def get_node(num=0, x=0, y=0):
        return {
            'num': num,
            'x': x,
            'y': y
        }

    # 定义个体
    @staticmethod
    def get_solution(path=None, sum=10.0, f=0.0, p=0.0, gen=0):
        if path is None:
            path = []
        return {
            'path': path,
            'sum': sum,
            'F': f,
            'P': p,
            'gen': gen,
        }

    @staticmethod
    def get_display():
        def init_pack():
            return [0.0, 0.0, 0.0, []]

        def init_cross_data():
            return [0, [], 0, [], []]

        def init_cross_action():
            return [0, False, 0.0, 0.0, init_cross_data()]

        def init_mutation_data():
            return [0, [], [], []]

        def init_mutation_action():
            return [0, False, 0.0, init_mutation_data()]

        def init_action():
            return [init_cross_action(), init_mutation_action(), 0]

        return {
            'gen': 0,
            'pack': [],
            'actions': [],
            'init_pack': init_pack,  # 返回函数引用
            'init_cross_data': init_cross_data,
            'init_cross_action': init_cross_action,
            'init_mutation_data': init_mutation_data,
            'init_mutation_action': init_mutation_action,
            'init_action': init_action,
        }

    # 计算两个城市之间的距离
    def distance_between(self, a, b):
        x = a['x'] - b['x']
        y = a['y'] - b['y']
        return math.ceil(math.sqrt(x ** 2 + y ** 2) / 10.0)  # 向上舍入

    # 计算个体解
    def sum(self, v):
        total = 0
        for i in range(1, len(v)):
            total += self.dis_map[v[i - 1]][v[i]]
            # total += random.randint(1, 10)
        return total

    def test_data(self, ):
        a = '测试用的'

    def coutPack(self, pack):
        a = '输出各基因的结果信息'

    # 初始化种群
    def init_packs(self, gen):
        self.packs = []
        for _ in range(self.pack_num):
            # 生成随机序列
            temp = self.get_solution(path=[self.start])
            random.shuffle(self.nums)
            temp['path'].extend(self.nums)
            temp['path'].append(self.goal)
            # 计算个体的解并将其压入种群
            temp['gen'] = gen
            temp['sum'] = self.sum(temp['path'])
            self.packs.append(temp)

        if gen == 1:
            greed = self.get_solution(path=[self.start])
            # is_visited = {key_node: False for key_node in self.key_nodes}
            # is_visited[self.start] = True
            # is_visited[self.goal] = True
            is_visited = {self.start: True, self.goal: True}
            # 通过贪心算法寻找两两节点之间最短距离，并组成路径
            for _ in range(len(self.nums)):
                min_dist = float('inf')
                min_node = None
                for index, dist in self.dis_map[greed['path'][-1]].items():
                    if not is_visited.get(index) and dist < min_dist:
                        min_dist = dist
                        min_node = index

                greed['path'].append(min_node)
                is_visited[min_node] = True

            greed['path'].append(self.goal)
            greed['gen'] = gen
            greed['sum'] = self.sum(greed['path'])
            self.packs[0] = greed

    # 传代
    def pass_on(self):
        self.record.append(self.packs[0]['sum'])
        # 对每一代的最优解进行记录，如果超过500代相同则进行传代操作
        # if len(self.record) > self.pack_num:
        if len(self.record) > self.pack_num:
            self.record.pop()
            # 传代后第一次变化前不进行传代，避免过早指数爆炸
            # if self.cur_cost != self.packs[0]['sum'] and self.record[0] == self.record[-1]:
            if self.packs[0]['sum'] == self.packs[-1]['sum']:
                print(f"{self.cur_gen}代中传代!")
                Prometheus = self.packs[0]['path']
                gen = self.packs[0]['gen']
                sum_ = self.packs[0]['sum']
                self.packs.clear()
                # 在最大传代限制前进行种群扩增
                if self.hay_flick > 0:
                    self.hay_flick -= 1
                    # self.pack_num = int(self.pack_num * math.log10(self.pack_num))
                    self.pack_num = self.pack_num * 10
                # 重新初始化种群，，并将火种压入
                self.init_packs(gen)
                self.packs[0]['path'] = Prometheus
                self.packs[0]['sum'] = sum_
                self.packs.sort(key=lambda x: x['sum'], reverse=False)
                self.cur_cost = sum_
                self.mutationP += 0.1
                self.pack_num = int(self.pack_num / 10)
                # 清空记录
                self.record.clear()

    # 交叉算子
    def cross(self, first_id, first_parent, second_id, second_parent):
        # print('=====================================')
        # print(f"{first_id}：交叉遗传；{first_id}，{second_id}")
        # print(f"父：{first_parent['path']}")
        # print(f"母：{second_parent['path']}")
        # 随机选择长度和起点，其中off是发生交叉的位置，length表示前length个基因片段一定继承于first_parent
        length = math.ceil(self.get_random_10000() * len(self.nums))
        off = self.get_random_node_size()
        next_gen = [-1] * len(first_parent['path'])
        next_gen[0] = self.start
        selected = {}  # 标记当前哪些巡检点已经走过
        parent1 = []  # 存储继承于first_parent的片段
        parent2 = []  # 存储继承于second_parent的片段
        # 初始化next_gen的off后的部分基因均来自first_parent
        for i in range(off, min(off + length, len(next_gen) - 1)):
            next_gen[i] = first_parent['path'][i]
            selected[next_gen[i]] = True
            parent1.append(first_parent['path'][i])
        # 修改next_gen的缺失的基因部分为second_gen，即交叉
        j = 1
        for i in range(1, len(next_gen)):
            # 若该基因片段未继承first_parent, 则尝试继承于second_parent
            if next_gen[i] == -1:
                for k in range(j, len(second_parent['path']) - 1):
                    # 若当前next_gen中包含second_parent的第k个基因片段数量为0，才继承该片段
                    # 这里是为了保证所有待巡检设备均通过，同时尽可能减少冗余路径
                    if second_parent['path'][k] not in selected:
                        next_gen[i] = second_parent['path'][k]
                        selected[second_parent['path'][k]] = True
                        parent2.append(second_parent['path'][k])
                        break
                j += 1
        next_gen[-1] = self.goal
        # next_gen.remove(-1)  # 删除未加入的基因，这些基因属于冗余基因，会导致个体重复遍历某个巡检点
        self.cross_data_temp = (first_id, parent1.copy(), second_id, parent2.copy(), next_gen.copy())
        # print(f"子：{next_gen}")
        # print(f"偏移起点：{off}；交叉长度；{length}")
        # print(f"父基因片段：{parent1}")
        # print(f"母基因片段：{parent2}")
        return self.get_solution(next_gen.copy(), self.sum(next_gen), 0.0, 0.0, first_parent['gen'] + 1)

    # 变异算子
    def mutation(self, first_id, cur):
        # print('=====================================')
        # print(f"{first_id}变异")
        # print(f"变异前：{cur['path']}")
        # 随机选择长度和起点，其中off是发生变异的位置，length表示前length个基因片段一定继承于first_parent
        length = math.ceil(self.get_random_10000() * len(self.key_nodes))
        off = self.get_random_node_size()
        off = 2 if off == 1 else off  # 防止off为1导致基因没有发生变化
        m = [self.start]  # 变异后的基因
        selected = {}  # 标记当前哪些巡检点已经走过
        mutation1 = []  # 存储移动到前面的片段
        mutation2 = []  # 存储移动到后面的片段
        # 初始化变异后的基因的off之前的片段来自cur的off之后的片段，故这里的变异仅仅把部分基因片段移动到前面
        for i in range(off, min(off + length, len(cur['path']) - 1)):
            m.append(cur['path'][i])
            selected[cur['path'][i]] = True
            mutation1.append(cur['path'][i])
        # 补上m路径中缺失的待巡检点，其中goal就本部分补上
        for i in range(1, len(cur['path'])):
            # 若selected中缺少cur中基因片段，则需要直接继承cur中对应片段
            if cur['path'][i] not in selected:
                m.append(cur['path'][i])
                mutation2.append(cur['path'][i])
        # 修改当前基因为变异后的信息
        cur['path'] = m
        cur['sum'] = self.sum(cur['path'])
        self.mutation_data_temp = (first_id, mutation1.copy(), mutation2.copy(), cur['path'].copy())
        # print(f"变异后：{cur['path']}")
        # print(f"变异起点：{off}；变异长度；{length}")
        # print(f"置前片段：{mutation1}")
        # print(f"置后片段：{mutation2}")

    # 变异算子 - 贪婪倒位 - 优化效率
    def g_mutation(self, cur):
        # 随机选择起点，找到距起点最近的点，然后将最近点到起点之间的段倒位
        selected = random.randint(2, len(self.key_nodes) - 4)
        selected_node = cur['path'][selected]
        min_dist = float('inf')
        min_node = None
        # 找到距离selected_node最近的node和dist
        for node_num, dist in self.dis_map[selected_node].items():
            if node_num != selected_node and dist < min_dist:
                min_dist = dist
                min_node = node_num
        # 找变异的起始点在cur的路径中位置
        begin, end = None, None
        for i in range(1, len(cur['path']) - 1):
            if cur['path'][i] == min_node:
                if i > selected + 1:
                    begin, end = selected + 1, i
                elif i < selected - 1:
                    begin, end = i, selected - 1
                break
        # 计算变异后的基因序列
        if begin is not None and end is not None:
            cur['path'][begin:end + 1] = reversed(cur['path'][begin:end + 1])
            cur['sum'] = self.sum(cur['path'])

    # 进化过程
    def process(self, cur_gen):
        random.seed(time.time())
        dis = self.get_display()
        dis = {key: dis[key] for key in ['gen', 'pack', 'actions']}
        dis["gen"] = cur_gen - 1
        total = 0  # 总适应度
        next_gen_packs = []  # 下一代种群
        # print(self.packs[0]['gen'], int(self.packs[0]['sum']))
        self.pass_on()  # 传代操作
        # 计算种群种每个个体的适应度
        for i in range(len(self.packs) - 1):  # 最后一个个体属于要淘汰的，不参与轮盘赌
            pack = self.packs[i]
            pack['F'] = self.BASE / pack['sum']
            pack['P'] = 0 if i == 0 else self.packs[i - 1]['P'] + pack['F']
            total += pack['F']
        self.packs[-1]['F'] = 0.0  # 最后一个个体属于要淘汰的，故置0
        self.packs[-1]['P'] = 0.0
        # 把种群信息写入dis中
        dis['pack'].append(self.packs.copy())  # 请注意，有些地方不能直接存引用，需要深拷贝------------------------------------
        # 最优个体直接进入下一代，防止反向进化
        next_gen_packs.append(self.packs[0].copy())
        next_gen_packs[0]['gen'] += 1
        # 交叉与变异操作：应用轮盘赌，选择交叉个体
        # 由于种群容量不变且最优个体占位，故每一代保留最优个体的同时，剔除最差个体
        # 即最差个体不参与轮盘赌交叉
        for i in range(len(self.packs) - 1):
            first_parent = self.packs[i].copy()
            first_id = i
            cross_p = self.get_random_10000()
            # 若本次p低于交叉概率，则对i进行交叉遗传
            if cross_p < self.crossP:
                # 选择前30%个个体，再按照适应度和另一个随机数选
                cross_parent_num = int((len(self.packs) - 1) * 0.3)
                if cross_parent_num < 2:
                    cross_parent_num = 2
                # while len(cross_parents) < cross_parent_num:
                #     num = random.randint(0, len(self.packs) - 2)
                #     if num not in cross_parents:
                #         cross_parents.append(num)
                packs_orderby_p = self.packs.copy()
                # packs_orderby_p.sort(key=lambda x: x['sum'], reverse=True)
                cross_parents = [i for i in range(cross_parent_num)]

                cross_parent_p = [packs_orderby_p[cross_parent]['sum'] for cross_parent in cross_parents]
                cross_parent_total_p = sum(cross_parent_p)
                is_cross = True
                p = self.get_random_10000()
                if cross_parent_total_p == 0:
                    is_cross = False
                else:
                    cross_parent_p = [p / cross_parent_total_p for p in cross_parent_p]
                    cross_parent_weight = [sum(cross_parent_p[0: i + 1]) for i in range(0, cross_parent_num)]
                    # 依概率选择一个祖宗
                    second_id = cross_parents[0]
                    for k in range(len(cross_parent_weight)):
                        if p < cross_parent_weight[k]:
                            second_id = cross_parents[k]
                            break
                    second_parent = packs_orderby_p[second_id].copy()
                    next_gen_packs.append(self.cross(first_id, first_parent, second_id, second_parent))

                # 找个适应度比随机数高的
                # second_id = 0
                # selected = self.get_random_10000() * total
                # is_cross = False
                # for j in range(len(self.packs) - 1):
                #     # 防止与自己进行交叉遗传
                #     if j == i:
                #         continue
                #     second_parent = self.packs[j]
                #     # 若该个体j被选择的概率大于于随机数，则对个体i和j进行交叉遗传
                #     if selected < second_parent['P']:
                #         second_id = j
                #         next_gen_packs.append(self.cross(first_id, first_parent, second_id, second_parent))
                #         is_cross = True
                #         break
                # 保存当前动作
                if not is_cross:
                    next_gen_packs.append(first_parent)
                # else:
                #     next_gen_packs.append(first_parent)
                self.cross_action_temp = (first_id, True, cross_p, p, self.cross_data_temp,
                                          {k: v for k, v in zip(cross_parents, cross_parent_p)}
                                          )
            # 不交叉遗传
            else:
                first_parent['gen'] += 1
                next_gen_packs.append(first_parent)
                # 保存当前动作
                self.cross_action_temp = (first_id, False, cross_p, 0.0, self.get_display()['init_cross_data'](), {})
            # 变异操作
            mutation_p = self.get_random_10000()
            if mutation_p < self.mutationP:
                # 当传代1次后变更算子到更高效的贪婪倒位
                # if len(self.key_nodes) > 6 and self.hay_flick < 6:
                #     self.g_mutation(next_gen_packs[-1])
                # else:
                #     self.mutation(first_id, next_gen_packs[-1]
                self.mutation(first_id, next_gen_packs[-1])
                self.mutation_action_temp = (first_id, True, mutation_p, self.mutation_data_temp)
            else:
                self.mutation_action_temp = (first_id, False, mutation_p, self.get_display()['init_mutation_data']())
            dis['actions'].append([self.cross_action_temp, self.mutation_action_temp, first_id])
        # 将本轮数据存入displays
        self.displays.append(dis)
        # 将next_gen_packs中的个体进行排序，以便找到最优
        next_gen_packs.sort(key=lambda x: x['sum'], reverse=False)
        next_gen_packs = next_gen_packs[: self.pack_num]
        return next_gen_packs

    # 执行算法
    def run(self):
        start_time = time.time()
        random.seed(time.time())

        self.init_packs(1)
        self.packs.sort(key=lambda x: x['sum'], reverse=False)

        while self.cur_gen <= self.max_gen:
            self.packs = self.process(self.cur_gen)
            self.cur_gen += 1

        elapsed_time = time.time() - start_time
        print("*****************遗传算法********************")
        print(f"总耗时: {elapsed_time:.2f} s")
        print(f"最短路径长度: {self.packs[0]['sum']}")
        print(" ".join(map(str, self.packs[0]['path'])))
        print("********************************************")

    def get_best_solution(self, ):
        return self.packs[0]['sum'], self.packs[0]['path']

# ga = TGP_GA()
# ga.run()
# print(ga.displays)
